/**
 * https://leetcode-cn.com/problems/climbing-stairs/
 * 爬楼梯
 * @param n 
 */
const climbStairs = (n: number): number => {
    // 台阶数小于2
    if (n < 2) return 1;

    // 初始值
    let prev = 1, // 前一个
        cur = 1, // 当前楼梯
        ans = 0

    // 从第二层开始算
    for (let i = 2; i <= n; i++) {
        ans = prev + cur;
        // 前一个等于当前的
        prev = cur;
        // 当前和赋给当前的
        cur = ans
    }

    return ans
};

// 动态规划
const climbStairs3 = (n: number): number => {
    // 台阶数小于2
    if (n < 2) return 1;

    // dp[i] 表示爬到第i层有多少种方法
    // dp[i] = dp[i - 1] + dp[i - 2]  第i层的方法数必定是爬到第i - 1层和爬到第i - 2的方法数
    const dp: number[] = new Array(n + 1);

    // 初始值
    dp[0] = 1;
    dp[1] = 1;

    // 从第二层开始算
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n]
};



// const climbStairs = (n: number): number => {
//     let p: number = 0, q: number = 0, ans: number = 1;
//     for (let i = 1; i <= n; i++) {
//         p = q
//         q = ans;
//         // f(n) = f(n - 1) + f(n - 2)
//         // 0 + 1
//         // 1 + 1
//         // 1 + 2 
//         // 2 + 3
//         // 3 + 5
//         // ...
//         ans = p + q;
//     }
//     return ans;
// };

// 递归法
const climbStairs2 = (n: number): number => {
    let count = 0;
    const dfs = (c: number) => {
        if (c < 0) return;

        // 达到边界条件, 可以计数
        if (c === 0) {
            count++
        }

        // 爬一个楼梯
        dfs(c - 1)

        // 爬两个
        dfs(c - 2)
    }

    dfs(n)

    return count;
};

console.log(climbStairs(44))